package com.gitee.feizns.explore.data_structure.linked_list.singly.splitListToParts;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;

/**
 * @author feizns
 * @since 2020/3/6
 */
public class SplitListToParts {

    public static void main(String[] args) {
        System.out.println(splitListToParts(create(), 2));
    }

    private static ListNode create() {
        ListNode ret = new ListNode(1);
        ret.next = new ListNode(2);
        ret.next.next = new ListNode(3);
        return ret;
    }

    public static ListNode[] splitListToParts(ListNode root, int k) {
        int[] lens = new int[k];
        int i = 0;
        for (ListNode tmp = root; tmp != null; tmp = tmp.next) {
            lens[i++]++;
            if ( i == k )
                i = 0;
        }

        ListNode[] ret = new ListNode[k];
        ListNode pre = new ListNode(-1);
        pre.next = root;
        ListNode start = root;
        ListNode end = root;
        for (int j = 0; j < ret.length; j++) {
            if ( lens[j] > 0 ) {
                for (int l = 1; l < lens[j]; l++)
                    end = end.next;
                ret[j] = start;
                start = end.next;
                end.next = null;
                end = start;
            }
        }
        return ret;
    }

}
